#include <iostream>
#include <cstdlib>
#include <limits>
#define BLACK false
#define RED true
#define MIN (std::numeric_limits<T>::min())
template <typename T>
    class Node
    {
    public:
	T data;
	Node<T>* lc;
	Node<T>* rc;
	Node<T>* parent;
        bool color = RED;
        Node(){parent = lc = rc = NULL;}
	Node(T _data);
        ~Node(){};
    };

template <typename T>
Node<T>::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template <typename T>
class BinaryTree
{
private:
    Node<T>* root;
    Node<T>* NIL;
    void inorder_walk(Node<T>* _x) const;
    void release(Node<T>* _x);
    Node<T>* tree_search(Node<T>* _x,T _data);
    void transplant(Node<T>* u, Node<T>* v);
    void leftrotate(Node<T> *_x);
    void rightrotate(Node<T> *_x);
    void rbinsert(Node<T> *_z);
    void rbinsertfixup(Node<T> *_z);
    void rbtransplant(Node<T>* u, Node<T>* v);
    void rbdelfixup(Node<T> *x);
    
    
public:

    BinaryTree() {NIL = new Node<T>;NIL->color = BLACK;NIL->data = MIN;root = NIL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    void inorder_walk() const;
    Node<T>* min(Node<T>* _x) const;
    Node<T>* max(Node<T>* _x) const;
    Node<T>* successor(Node<T>* _x) const;
    Node<T>* predecessor(Node<T>* _x) const;
    Node<T>* tree_search(T _data);
    void BSTSORT(T* _A, int n);
    void tree_delete(Node<T>* z);
    void rbdel(Node<T> *_z);
    void rbinsert(T _data);
};


template <typename T>
void BinaryTree<T>::release(Node<T>* _x)
{
    if (_x != NIL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};
template <typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
    delete NIL;
};

template <typename T>
Node<T>* BinaryTree<T>::successor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if (x->rc != NIL)
	return min(x->rc);
    Node<T>* y = x->parent;
    while (y != NIL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};
template <typename T>
Node<T>* BinaryTree<T>::predecessor(Node<T>* _x) const
{
  Node<T>* x = _x;
  if(x->lc != NIL)
      return max(x->lc);
  Node<T>* y = x->parent;
  while(y != NIL && x == y->lc)
  {
     x = y;
     y = y->parent;
  }
  return y;
};

template <typename T>
Node<T>* BinaryTree<T>::min(Node<T>* _x) const
{
    while (_x->lc != NIL)
	_x = _x->lc;
    return _x;
};
template <typename T>
Node<T>* BinaryTree<T>::max(Node<T>* _x) const
{
    while (_x->rc != NIL)
	_x = _x->rc;
    return _x;
};
template <typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};
template <typename T>
void BinaryTree<T>::inorder_walk(Node<T>* _x) const
{
    if (_x != NIL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "  ";
	inorder_walk(_x->rc);
    }
};
template <typename T>
void BinaryTree<T>::insert(T _data)
{
    Node<T>* y = NIL;
    Node<T>* x = root;
    Node<T>* p = new Node<T>(_data);
    while (x != NIL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    p->parent = y;
    if (y == NIL)
	root = p;
    else if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
};

template <typename T>
Node<T>* BinaryTree<T>::tree_search(T _data)
{
  tree_search(root,_data);
}

template <typename T>
Node<T>* BinaryTree<T>::tree_search(Node<T>* _x,T _data)
{
  if(_x == NIL || _data == _x->data)
    return _x;
  if(_data < _x->data)
  return tree_search(_x->lc,_data);
  else
  return tree_search(_x->rc,_data);
}

template <typename T>
void BinaryTree<T>::BSTSORT(T* _A, int n)
{
 BinaryTree<T> A;
 int i;
 for(i=0; i<n; i++)
 A.insert(_A[i]);
 A.inorder_walk();
}



template <typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    NIL = new Node<T>;
    NIL->color = BLACK;
    NIL->data = MIN;
    Node<T> *r = new Node<T>;
    r->data = _data;
    r->lc = NIL;
    r->rc = NIL;
    r->parent = NIL;
    root = r;
};

template <typename T>
void BinaryTree<T>::transplant(Node<T>* u, Node<T>* v)
{
   if(u->parent == NIL)
   root = v;
   else if(u == u->parent->lc)
   u->parent->lc = v;
   else u->parent->rc = v;
   if(v != NIL)
   v->parent = u->parent;
}

template <typename T>
void BinaryTree<T>::rightrotate(Node<T> *_x)
{
    Node<T> *y = _x->lc;
    _x->lc = y->rc;
    if (y->rc != NIL)
	y->rc->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == NIL)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->lc)
	// set y as _x's parent's left child.
	_x->parent->lc = y;
    else
	_x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
};

template <typename T>
void BinaryTree<T>::leftrotate(Node<T> *_x)
{
    Node<T> *y = _x->rc;
    _x->rc = y->lc;
    if (y->lc != NIL)
	y->lc->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == NIL)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->lc)
	// set y as _x's parent's left child.
	_x->parent->lc = y;
    else
	_x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
};
template <typename T>
void BinaryTree<T>::tree_delete(Node<T>* z)
{
   if(z->lc == NIL)
   transplant(z, z->rc);
   else if(z->rc == NIL)
   tansplant(z, z->lc);
   else
   {
    Node<T>* y;
    y = min(z->rc);
    if(y->parent != z)
    {
      transplant(y, y->rc);
      y->rc = z->rc;
      y->rc->parent = y;
    }
    transplant(z, y);
    y->lc = z->lc;
    y->lc->parent = y;
   }
}
template <typename T>
void BinaryTree<T>::rbinsert(Node<T> *_z)
{
   Node<T> *y;
   Node<T> *x;
   y = NIL;
   x = root;
   while(x != NIL)
   {
      y = x;
      if(_z->data < x->data)
      x = x->lc;
      else x = x->rc;
   }
   _z->parent = y;
   if(y == NIL)
   root = _z;
   else if(_z->data < y->data)
   y->lc = _z;
   else y->rc = _z;
   _z->lc = NIL;
   _z->rc = NIL;
   _z->color = RED;
   rbinsertfixup(_z);
  
}

template <typename T>
void BinaryTree<T>::rbinsertfixup(Node<T> *_z)
{
   while(_z->parent->color == RED)
   if (_z->parent == _z->parent->parent->lc)
	{
	    // y is the uncle of x.
	    Node<T> *y = _z->parent->parent->rc;
	    // case I:
	    if (y->color == RED)
	    {
		_z->parent->color = y->color = BLACK;
		_z->parent->parent->color = RED;
		_z = _z->parent->parent;
		if (_z->parent->color == BLACK)
		    break;
	    }
	    // y->color == BLACK.
	    else
	    {
		// tortuous...
		if (_z == _z->parent->rc)
		{
		    // case II:
                    _z = _z->parent;
		    leftrotate(_z);
		}
		// case III:
                _z->parent->color = BLACK;
                _z->parent->parent->color = RED;
		rightrotate(_z->parent->parent);
	    }
	}
    	else if (_z->parent == _z->parent->parent->rc)
	{
	    Node<T> *y = _z->parent->parent->lc;
	    // case I:
	    if (y->color == RED)
	    {
		_z->parent->color = y->color = BLACK;
		_z->parent->parent->color = RED;
		_z = _z->parent->parent;
		if (_z->parent->color == BLACK)
		    break;
	    }
	    else
	    {
		if (_z == _z->parent->lc)
		{
		    // case II:
                    _z = _z->parent;
		    rightrotate(_z);
		}
		// case III:
                _z->parent->color = BLACK;
                _z->parent->parent->color = RED;
		leftrotate(_z->parent->parent);
	
	    }
	}
    root->color = BLACK;
}

template <typename T>
void BinaryTree<T>::rbinsert(T _data)
{
    Node<T> *x = new Node<T>(_data);
    rbinsert(x);
}






template <typename T>
void BinaryTree<T>::rbtransplant(Node<T>* u, Node<T>* v)
{
    if(u->parent == NIL)
     root = v;
    else if(u == u->parent->lc)
     u->parent->lc = v;
    else u->parent->rc = v;
    v->parent = u->parent;
}
  
template <typename T>
void BinaryTree<T>::rbdel(Node<T> *_z)
{
    Node<T> *y = _z;
    bool original_color_y = y->color;
    Node<T> *x;
    if (_z->lc == NIL)
    {
	x = _z->rc;
	rbtransplant(_z, _z->rc);
    }
    else if (_z->rc == NIL)
    {
	x = _z->lc;
	rbtransplant(_z, _z->lc);
    }
    else
    {
    	y = min(_z->rc);
    	original_color_y = y->color;
    	x = y->rc;
//    	if (y->parent == _z)
//    	    x->parent = y;
//    	else
	if (y->parent != _z)
    	{
    	    rbtransplant(y, y->rc);
    	    y->rc = _z->rc;
    	    y->rc->parent = y;
    	}
    	rbtransplant(_z, y);
    	y->lc = _z->lc;
    	y->lc->parent = y;
    	y->color = _z->color;
    }
    if (original_color_y == BLACK)
     	rbdelfixup(x);
}


template <typename T>
void BinaryTree<T>::rbdelfixup(Node<T> *x)
{
    while (x != root && x->color == BLACK)
    	    if (x == x->parent->lc)
    	    {
    		Node<T> *w = x->parent->rc;
    		if (w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    leftrotate(x->parent);
    		    w = x->parent->rc;
    		}
    		if (w->lc->color == BLACK && w->rc->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
		{
		    if (w->rc->color == BLACK)
		    {
			w->lc->color = BLACK;
			w->color = RED;
			rightrotate(w);
			w = x->parent->rc;
		    }
		    w->color = x->parent->color;
		    x->parent->color = BLACK;
		    w->rc->color = BLACK;
		    leftrotate(x->parent);
		    // If job finished, but x is not root, set to root
		    // for quitting.
		    x = root;
		}
	    }
	    else
     	    {
    		Node<T> *w = x->parent->lc;
    		if (w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    rightrotate(x->parent);
    		    w = x->parent->lc;
    		}
    		if (w->rc->color == BLACK && w->lc->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
		{
		    if (w->lc->color == BLACK)
		    {
			w->rc->color = BLACK;
			w->color = RED;
			leftrotate(w);
			w = x->parent->lc;
		    }
		    w->color = x->parent->color;
		    x->parent->color = BLACK;
		    w->lc->color = BLACK;
		    rightrotate(x->parent);
		    // If job finished, but x is not root, set to root
		    // for quitting.
		    x = root;
		}
     	    }
    x->color = BLACK;   
}








